//?
function isBalanced(root: TreeNode | null): boolean {
    function getDepth(root: TreeNode | null): number {
        if (root === null) return 0;
        let leftDepth: number = getDepth(root.left);
        if (leftDepth === -1) return -1;
        let rightDepth: number = getDepth(root.right);
        if (rightDepth === -1) return -1;
        if (Math.abs(leftDepth - rightDepth) > 1) return -1;
        return 1 + Math.max(leftDepth, rightDepth);
    }
    return getDepth(root) !== -1;
};
//leetcode submit region end(Prohibit modification and deletion)
// 后序遍历递归
function isBalanced2(root: TreeNode | null): boolean {
    if (!root) return true
    let res = true
    //? 后序遍历
    function dfs(root) {
        //? 计算左右的深度
        let left = root.left && dfs(root.left) + 1
        let right = root.right && dfs(root.right) + 1
        if (Math.abs(left - right) > 1) {
            res = false
        }
        //? 这个是用来控制返回左还是右的 因为一个根的高度是由更高的子树来决定的
        return Math.max(left, right)
    }
    dfs(root)
    return res
};
